home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Demos / OOFILE / Buildable, limited OOFILE / OOFILE partial source / ooflist.cpp < prev    next >
Encoding:
Text File  |  1995-09-26  |  7.0 KB  |  251 lines  |  [TEXT/CWIE]
  1. // Start of bit added by Ken
  2.  
  3. #include "ooflist.hpp"
  4.  
  5. // -------------------------------------------------------
  6. //  O O F I L E _ L i s t E l e m e n t
  7. // -------------------------------------------------------
  8.  
  9. OOF_ListElement::OOF_ListElement(unsigned long theItem)
  10. {
  11.      mItem = theItem;
  12.      mNext = 0;    // assume we'll put it at the end of the list 
  13. }
  14.  
  15. // -------------------------------------------------------
  16. //  O O F I L E _ L i s t
  17. // -------------------------------------------------------
  18.  
  19. //----------------------------------------------------------------------
  20. // OOF_List::OOF_List
  21. //    Initialize a list, empty to start with.
  22. //    Elements can now be added to the list.
  23. //----------------------------------------------------------------------
  24.  
  25. OOF_List::OOF_List()
  26. { 
  27.         mCount = 0;
  28.         mFirst = mLast = 0; 
  29. }
  30.  
  31. //----------------------------------------------------------------------
  32. // OOF_List::~OOF_List
  33. //    prepare a list for deallocation.  If the list still contains any 
  34. //    ListElements, de-allocate them.  However, note that we do *not*
  35. //    de-allocate the "items" on the list -- this module allocates
  36. //    and de-allocates the ListElements to keep track of each item,
  37. //    but a given item may be on multiple lists, so we can't
  38. //    de-allocate them here.
  39. //----------------------------------------------------------------------
  40.  
  41. OOF_List::~OOF_List()
  42. { 
  43.     while (remove() != 0)
  44.     ;     // delete all the list elements
  45. }
  46.  
  47. //----------------------------------------------------------------------
  48. // OOF_List::append
  49. //      append an "item" to the end of the list.
  50. //      
  51. //    Allocate a ListElement to keep track of the item.
  52. //      If the list is empty, then this will be the only element.
  53. //    Otherwise, put it at the end.
  54. //
  55. //    "item" is the thing to put on the list, it can be a pointer to 
  56. //        anything.
  57. //----------------------------------------------------------------------
  58.  
  59. void
  60. OOF_List::append(unsigned long theItem)
  61. {
  62.     OOF_ListElement *element = new OOF_ListElement(theItem);
  63.  
  64.         mCount++;
  65.     if (isEmpty()) {        // list is empty
  66.             mFirst = element;
  67.             mLast = element;
  68.     } else {            // else put it after last
  69.             mLast->mNext = element;
  70.             mLast = element;
  71.     }
  72. }
  73.  
  74. //----------------------------------------------------------------------
  75. // OOF_List::prepend
  76. //      Put an "item" on the front of the list.
  77. //      
  78. //    Allocate a ListElement to keep track of the item.
  79. //      If the list is empty, then this will be the only element.
  80. //    Otherwise, put it at the beginning.
  81. //
  82. //    "item" is the thing to put on the list, it can be a pointer to 
  83. //        anything.
  84. //----------------------------------------------------------------------
  85.  
  86. void
  87. OOF_List::prepend(unsigned long theItem)
  88. {
  89.     OOF_ListElement *element = new OOF_ListElement(theItem);
  90.  
  91.         mCount++;
  92.     if (isEmpty()) {        // list is empty
  93.             mFirst = element;
  94.             mLast = element;
  95.     } else {                        // else put it before first
  96.             element->mNext = mFirst;
  97.             mFirst = element;
  98.     }
  99. }
  100.  
  101. //----------------------------------------------------------------------
  102. // OOF_List::remove
  103. //      remove the first "item" from the front of the list.
  104. // 
  105. // Returns:
  106. //    Removed item, 0 if nothing on the list.
  107. //----------------------------------------------------------------------
  108.  
  109. unsigned long
  110. OOF_List::remove()
  111. {
  112.     OOF_ListElement *element = mFirst;
  113.     unsigned long thing;
  114.  
  115.     if (isEmpty()) 
  116.             return 0;
  117.  
  118.     thing = mFirst->mItem;
  119.     if (mFirst == mLast) {    // list had one item, now has none 
  120.         mFirst = 0;
  121.                 mLast = 0;
  122.     } else {
  123.         mFirst = element->mNext;
  124.     }
  125.         mCount--;
  126.     delete element;
  127.     return thing;
  128. }
  129.  
  130. //----------------------------------------------------------------------
  131. // OOF_List::isEmpty
  132. //      Returns true if the list is empty (has no items).
  133. //----------------------------------------------------------------------
  134.  
  135. bool
  136. OOF_List::isEmpty() const
  137. { 
  138.     if (mFirst == 0)
  139.         return true;
  140.     else
  141.     return false; 
  142. }
  143.  
  144. //----------------------------------------------------------------------
  145. // OOF_List::member
  146. //      Returns true if the list contains theItem.
  147. //----------------------------------------------------------------------
  148.  
  149. bool
  150. OOF_List::member(unsigned long theItem) const
  151. { 
  152.     if (mFirst != 0)
  153.         {
  154.               OOF_ListElement *ptr;        // keep track
  155.  
  156.               for (ptr = mFirst; ptr->mNext != 0; ptr = ptr->mNext)
  157.                 {
  158.                         if(ptr->mItem == theItem)
  159.                             return(true);
  160.                 }
  161.         }
  162.         return false;
  163. }
  164.  
  165. //----------------------------------------------------------------------
  166. // OOF_List::sortedInsert
  167. //      Insert an "item" into a list, so that the list elements are
  168. //    sorted in increasing order.
  169. //      
  170. //    Allocate a ListElement to keep track of the item.
  171. //      If the list is empty, then this will be the only element.
  172. //    Otherwise, walk through the list, one element at a time,
  173. //    to find where the new item should be placed.
  174. //----------------------------------------------------------------------
  175.  
  176. void
  177. OOF_List::sortedInsert(unsigned long theItem)
  178. {
  179.     OOF_ListElement *element = new OOF_ListElement(theItem);
  180.     OOF_ListElement *ptr;        // keep track
  181.  
  182.         mCount++;
  183.     if (isEmpty()) {    // if list is empty, put
  184.         mFirst = element;
  185.         mLast = element;
  186.     } else if (theItem < mFirst->mItem) {    
  187.                 // item goes on front of list
  188.             element->mNext = mFirst;
  189.             mFirst = element;
  190.         } else {        // look for mFirst one in list bigger than item
  191.           for (ptr = mFirst; ptr->mNext != 0; ptr = ptr->mNext) {
  192.               if (theItem < ptr->mNext->mItem) {
  193.                         element->mNext = ptr->mNext;
  194.                       ptr->mNext = element;
  195.                         return;
  196.                 }
  197.             }
  198.             mLast->mNext = element;        // item goes at end of list
  199.             mLast = element;
  200.     }
  201. }
  202.  
  203. //----------------------------------------------------------------------
  204. // List::sortedInsertNoDups
  205. //      Insert an "item" into a list, so that the list elements are
  206. //    sorted in increasing order and there are no duplicates.
  207. //      
  208. //    Allocate a ListElement to keep track of the item.
  209. //      If the list is empty, then this will be the only element.
  210. //    Otherwise, walk through the list, one element at a time,
  211. //    to find where the new item should be placed.
  212. //----------------------------------------------------------------------
  213.  
  214. void
  215. OOF_List::sortedInsertNoDups(unsigned long theItem)
  216. {
  217.     OOF_ListElement *element = new OOF_ListElement(theItem);
  218.     OOF_ListElement *ptr;        // keep track
  219.  
  220.     if (isEmpty()) {    // if list is empty, put
  221.         mFirst = element;
  222.         mLast = element;
  223.         } else if (theItem < mFirst->mItem) {    
  224.             // item goes on front of list
  225.                 element->mNext = mFirst;
  226.                 mFirst = element;
  227.         } else {        // look for first one in list bigger than item
  228.           for (ptr = mFirst; ptr->mNext != 0; ptr = ptr->mNext) {
  229.               if (theItem < ptr->mNext->mItem) {
  230.                         if (theItem == ptr->mItem) {
  231.                             delete element;
  232.                             return;
  233.                         } else {
  234.                             element->mNext = ptr->mNext;
  235.                         ptr->mNext = element;
  236.                             mCount++;
  237.                             return;
  238.                         }
  239.                 }
  240.             }
  241.             mLast->mNext = element;        // item goes at end of list
  242.             mLast = element;
  243.         }
  244. }
  245.  
  246. unsigned long OOF_List::count() const
  247. {
  248.     return mCount;
  249. }
  250. // End of bit added by Ken
  251.